0284. 窥视迭代器【中等】
1. 📝 题目描述
请你在设计一个迭代器,在集成现有迭代器拥有的 hasNext 和 next 操作的基础上,还额外支持 peek 操作。
实现 PeekingIterator 类:
PeekingIterator(Iterator<int> nums)使用指定整数迭代器nums初始化迭代器。int next()返回数组中的下一个元素,并将指针移动到下个元素处。bool hasNext()如果数组中存在下一个元素,返回true;否则,返回false。int peek()返回数组中的下一个元素,但 不 移动指针。
注意:每种语言可能有不同的构造函数和迭代器 Iterator,但均支持 int next() 和 boolean hasNext() 函数。
示例 1:
txt
输入:
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
输出:
[null, 1, 2, 2, 3, false]
解释:
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next(); // 返回 1,指针移动到下一个元素 [1,2,3]
peekingIterator.peek(); // 返回 2,指针未发生移动 [1,2,3]
peekingIterator.next(); // 返回 2,指针移动到下一个元素 [1,2,3]
peekingIterator.next(); // 返回 3,指针移动到下一个元素 [1,2,3]
peekingIterator.hasNext(); // 返回 False1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
提示:
1 <= nums.length <= 10001 <= nums[i] <= 1000- 对
next和peek的调用均有效 next、hasNext和peek最多调用1000次
进阶:你将如何拓展你的设计?使之变得通用化,从而适应所有的类型,而不只是整数型?
2. 🎯 s.1 - 缓存下一个元素
c
struct PeekingIterator {
struct Iterator* iterator;
int peeked;
bool hasPeeked;
};
struct PeekingIterator* Constructor(struct Iterator* iter) {
struct PeekingIterator* pIter = (struct PeekingIterator*)malloc(sizeof(struct PeekingIterator));
pIter->iterator = iter;
pIter->hasPeeked = false;
return pIter;
}
int peek(struct PeekingIterator* obj) {
if (!obj->hasPeeked) {
obj->peeked = Iterator_next(obj->iterator);
obj->hasPeeked = true;
}
return obj->peeked;
}
int next(struct PeekingIterator* obj) {
if (obj->hasPeeked) {
obj->hasPeeked = false;
return obj->peeked;
}
return Iterator_next(obj->iterator);
}
bool hasNext(struct PeekingIterator* obj) {
return obj->hasPeeked || Iterator_hasNext(obj->iterator);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
js
/**
* @param {Iterator} iterator
*/
var PeekingIterator = function (iterator) {
this.iterator = iterator
this.peeked = null
this.hasPeeked = false
}
/**
* @return {number}
*/
PeekingIterator.prototype.peek = function () {
if (!this.hasPeeked) {
this.peeked = this.iterator.next()
this.hasPeeked = true
}
return this.peeked
}
/**
* @return {number}
*/
PeekingIterator.prototype.next = function () {
if (this.hasPeeked) {
this.hasPeeked = false
return this.peeked
}
return this.iterator.next()
}
/**
* @return {boolean}
*/
PeekingIterator.prototype.hasNext = function () {
return this.hasPeeked || this.iterator.hasNext()
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
py
class PeekingIterator:
def __init__(self, iterator):
self.iterator = iterator
self.peeked = None
self.has_peeked = False
def peek(self):
if not self.has_peeked:
self.peeked = self.iterator.next()
self.has_peeked = True
return self.peeked
def next(self):
if self.has_peeked:
self.has_peeked = False
return self.peeked
return self.iterator.next()
def hasNext(self):
return self.has_peeked or self.iterator.hasNext()1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
- 时间复杂度:每个操作均为
- 空间复杂度:
,只缓存一个元素
算法思路:
- 用一个变量缓存
peek的结果,配合布尔标记记录是否已缓存 peek时若未缓存则调用next并存储,next时优先返回缓存值